package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-10 09:59:48
 */
class Q0033_SearchInRotatedSortedArray {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            int start = 0;
            int end = nums.length - 1;
            if (target > nums[end] && target < nums[start]) return -1;
            while (start <= end) {
                if (nums[start] == target) return start;
                if (nums[end] == target) return end;
                int mid = start + ((end - start) >> 1);
                if (nums[mid] == target) return mid;

                if (nums[start] < nums[end]) {
                    // �� start ~ end ��Χ��û����ת
                    if (target < nums[mid]) {
                        start++;
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                        end--;
                    }
                } else {
                    // �� start ~ end ��Χ������ת
                    if (nums[start] < nums[mid]) {
                        // �� start ~ mid ��Χ��û����ת
                        if (target < nums[mid] && target > nums[start]) {
                            // target �ڷ�Χ��
                            start++;
                            end = mid;
                        } else {
                            start = mid + 1;
                            end--;
                        }
                    } else {
                        // �� start ~ mid ��Χ������ת
                        if (target < nums[mid] && target < nums[start] || target > nums[mid] && target > nums[start]) {
                            // target �ڷ�Χ��
                            start++;
                            end = mid;
                        } else {
                            start = mid + 1;
                            end--;
                        }
                    }
                }
            }

            return -1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0033_SearchInRotatedSortedArray().new Solution();
        System.out.println(solution.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        System.out.println(solution.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        System.out.println(solution.search(new int[]{6, 7, 1, 2, 3, 4, 5}, 3));
        System.out.println(solution.search(new int[]{3, 4, 5, 6, 7, 1, 2}, 4));
        System.out.println(solution.search(new int[]{5, 1, 2, 3, 4}, 1));

    }
}